/*
 * @LastEditTime: 2023-03-31 23:24:10
 * @Method: 
 * @Description: 
 */
package CodeTop;

class Solution124 {
    int maxVal = Integer.MIN_VALUE;

    public int maxPathSum(TreeNode root) {
        dfs(root);
        return maxVal;
    }

    public int dfs (TreeNode node) {
        if (node == null) {
            return 0;
        }
        int val = node.val;
        int l = dfs(node.left);
        int r = dfs(node.right);
        if (l > 0) {
            val += l;
        }
        if (r > 0) {
            val += r;
        }
        maxVal = Math.max(maxVal, val);
        return node.val + Math.max(0, Math.max(l, r));
    }
}